package 二叉树层序遍历.二叉树的右视图;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Solution {
    /*
    给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
     */
    public List<Integer> rightSideView(TreeNode root) {
        // 利于层序遍历解决问题
        // 题目的意思即需要记录层序遍历的每一层的最后一个节点

        if (root == null)
            return Collections.emptyList();
        List<Integer> list = new ArrayList<>();
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        TreeNode p, last = root;
        while (!queue.isEmpty()) {
            // 从队头弹出一个节点
            p = queue.poll();
            if(p.left!=null) queue.offer(p.left);
            if(p.right!=null) queue.offer(p.right);
            if(p == last){
                list.add(p.val);
                last = queue.peekLast();
            }
        }
        return list;
    }
}
